{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Distant Barcodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #counting #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #计数 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rearrangeBarcodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #距离相等的条形码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个仓库里，有一排条形码，其中第 <code>i</code> 个条形码为&nbsp;<code>barcodes[i]</code>。</p>\n",
    "\n",
    "<p>请你重新排列这些条形码，使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案，此题保证存在答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>barcodes = [1,1,1,2,2,2]\n",
    "<strong>输出：</strong>[2,1,2,1,2,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>barcodes = [1,1,1,1,2,2,3,3]\n",
    "<strong>输出：</strong>[1,3,1,3,2,1,2,1]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= barcodes.length &lt;= 10000</code></li>\n",
    "\t<li><code>1 &lt;= barcodes[i] &lt;= 10000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [distant-barcodes](https://leetcode.cn/problems/distant-barcodes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [distant-barcodes](https://leetcode.cn/problems/distant-barcodes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,1,2,2,2]', '[1,1,1,1,2,2,3,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        for i in range(len(barcodes) - 1):\n",
    "            if barcodes[i] != barcodes[i+1]:\n",
    "                continue\n",
    "            j = i +2  \n",
    "            while j < len(barcodes) and barcodes[i] == barcodes[j]:\n",
    "                    j += 1\n",
    "            if j == len(barcodes):\n",
    "                break\n",
    "            barcodes[i + 1], barcodes[j] = barcodes[j], barcodes[i + 1]\n",
    "        \n",
    "        for i in range(len(barcodes) - 1, 1, -1):\n",
    "            if barcodes[i] != barcodes[i-1]:\n",
    "                continue\n",
    "            j = i - 2\n",
    "            while barcodes[i] == barcodes[j]:\n",
    "                j -= 1\n",
    "            barcodes[i - 1], barcodes[j] = barcodes[j], barcodes[i - 1]\n",
    "        return barcodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        def left_check(barcodes):\n",
    "            l_b = len(barcodes)\n",
    "            for i, code in enumerate(barcodes):\n",
    "                if i == 0 or i == l_b - 1:\n",
    "                    continue\n",
    "                if code == barcodes[i - 1]:\n",
    "                    j = i\n",
    "                    while j < l_b-1 and barcodes[j] == code:\n",
    "                        j += 1\n",
    "                    barcodes[i], barcodes[j] = barcodes[j], barcodes[i]\n",
    "            return barcodes\n",
    "        left_check(barcodes)\n",
    "        return left_check(barcodes[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        双指针插入\n",
    "        :param barcodes:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        i, cnt = 0, len(barcodes)\n",
    "        while i < cnt:\n",
    "            if (i == 0 or barcodes[i] != barcodes[i - 1]) and (i + 1 == cnt or barcodes[i] != barcodes[i + 1]):\n",
    "                i += 1\n",
    "            else:\n",
    "                tmp = barcodes.pop(i)\n",
    "                for j in range(-1, cnt - 1):\n",
    "                    if (j == -1 or barcodes[j] != tmp) and (j + 2 == cnt or barcodes[j + 1] != tmp):\n",
    "                        barcodes.insert(j + 1, tmp)\n",
    "                        break\n",
    "        return barcodes\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "\n",
    "        ## 技术模拟hash题目  任意两个相邻的条形码不能相等\n",
    "        ## 用个双端队列\n",
    "        \n",
    "        # ## \n",
    "        # deq = deque()\n",
    "        # dic = defaultdict(int)\n",
    "        # for n in barcodes:\n",
    "        #     dic[n] += 1\n",
    "        # ma = -1\n",
    "        # for i,v in dic.items():\n",
    "        #     if v > ma:\n",
    "        #         ma = v\n",
    "        #         deq.appendleft((i,v))\n",
    "        #         continue\n",
    "        #     deq.append((i,v))\n",
    "\n",
    "        # n = len(barcodes)\n",
    "        # ans = [0] * n\n",
    "        # tag = True\n",
    "        # for i in range(n):\n",
    "        #     if tag:\n",
    "        #         val, cnt = deq.popleft()\n",
    "        #     else:\n",
    "        #         val, cnt = deq.pop()\n",
    "        #     ans[i] = val\n",
    "        #     cnt -= 1\n",
    "        #     if cnt:\n",
    "        #         if tag:\n",
    "        #             deq.appendleft((val,cnt))\n",
    "        #         else:\n",
    "        #             deq.append((val,cnt))\n",
    "        #         tag = not tag\n",
    "        # return ans\n",
    "        ## 我擦嘞 这样不行 好像要考虑一下顺序\n",
    "\n",
    "        ## \n",
    "        ## \n",
    "\n",
    "\n",
    "        ## \n",
    "        n = len(barcodes)\n",
    "        j = n\n",
    "        for i in range(n-1):\n",
    "            if barcodes[i] != barcodes[i+1]:\n",
    "                continue\n",
    "            j = i+2\n",
    "            while j<n and barcodes[j] == barcodes[i]:\n",
    "                j += 1\n",
    "            if j == n:\n",
    "                break\n",
    "            barcodes[i+1],barcodes[j] = barcodes[j],barcodes[i+1]\n",
    "        if j != n:\n",
    "            return barcodes\n",
    "        \n",
    "        for i in range(n-1,0,-1):\n",
    "            if barcodes[i] != barcodes[i-1]:\n",
    "                continue\n",
    "            j = i-2\n",
    "            while j>=0 and barcodes[j] == barcodes[i]:\n",
    "                j -= 1\n",
    "            if j < 0:\n",
    "                break\n",
    "            barcodes[i-1], barcodes[j] = barcodes[j], barcodes[i-1]\n",
    "\n",
    "        return barcodes\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n=len(barcodes)\n",
    "        for i in range(n-1):\n",
    "            if barcodes[i]==barcodes[i+1]:\n",
    "                j=i+2\n",
    "                while j<n:\n",
    "                    if barcodes[j]!=barcodes[i+1]:\n",
    "                        barcodes[j],barcodes[i+1]=barcodes[i+1],barcodes[j]\n",
    "                        break\n",
    "                    j+=1\n",
    "            \n",
    "        for i in range(n-1,0,-1):\n",
    "            if barcodes[i]==barcodes[i-1]:\n",
    "                j=i-2\n",
    "                while j>=0:\n",
    "                    if barcodes[j]!=barcodes[i-1]:\n",
    "                        barcodes[j],barcodes[i-1]=barcodes[i-1],barcodes[j]\n",
    "                        break\n",
    "                    j-=1\n",
    "        \n",
    "        return barcodes\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        cnt = len(barcodes)\n",
    "        i = 0\n",
    "        while i < cnt:\n",
    "            if (i == 0 or barcodes[i] != barcodes[i - 1]) and (i + 1 == cnt or barcodes[i] != barcodes[i + 1]):\n",
    "                i += 1\n",
    "                continue\n",
    "            else:\n",
    "                tmp = barcodes.pop(i)\n",
    "                for j in range(-1, cnt - 1):\n",
    "                    if (j == -1 or tmp != barcodes[j]) and (j + 2 == cnt or tmp != barcodes[j + 1]):\n",
    "                        barcodes.insert(j + 1, tmp)\n",
    "                        break\n",
    "                            \n",
    "        return barcodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        \n",
    "        for i in range(len(barcodes)-1):\n",
    "            cur = barcodes[i]\n",
    "            if barcodes[i+1] == cur:\n",
    "                for j in range(i+2, len(barcodes)):\n",
    "                    if barcodes[j] != cur:\n",
    "                        barcodes[i+1], barcodes[j] = barcodes[j], barcodes[i+1]\n",
    "                        break\n",
    "        # print(barcodes)\n",
    "        \n",
    "\n",
    "\n",
    "        for i in range(len(barcodes)-1, 0, -1):\n",
    "            cur = barcodes[i]\n",
    "            if barcodes[i-1] == cur:\n",
    "                for j in range(i-2, -1, -1):\n",
    "                    # print(j, barcodes[j])\n",
    "                    if barcodes[j] != cur:\n",
    "                        barcodes[i-1], barcodes[j] = barcodes[j], barcodes[i-1]\n",
    "                        break\n",
    "        \n",
    "        # print(barcodes)\n",
    "\n",
    "\n",
    "        return barcodes\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes):\n",
    "        if len(barcodes) == 1 & len(barcodes) == 2:\n",
    "            return barcodes\n",
    "        up = 2\n",
    "        low = 1\n",
    "        cleck = 1\n",
    "        stop = 0\n",
    "        while up < len(barcodes) and stop < 10:\n",
    "            if barcodes[low] != barcodes[low-1]:\n",
    "                low += 1\n",
    "                up += 1\n",
    "                if up == len(barcodes) and low < len(barcodes) - 2:\n",
    "                    up = low + 1\n",
    "                    stop += 1\n",
    "                continue\n",
    "            elif barcodes[up] == barcodes[low-1]:\n",
    "                up += 1\n",
    "                if up == len(barcodes) and low < len(barcodes) - 2:\n",
    "                    up = low + 1\n",
    "                    stop += 1\n",
    "                continue\n",
    "            elif barcodes[up] != barcodes[low-1]:\n",
    "                l = barcodes[low]\n",
    "                u = barcodes[up]\n",
    "                barcodes[low] = u\n",
    "                barcodes[up] = l\n",
    "                low += 1\n",
    "                up += 1\n",
    "                if up == len(barcodes) and low < len(barcodes) - 2:\n",
    "                    up = low + 1\n",
    "                    stop += 1\n",
    "        while cleck < len(barcodes):\n",
    "            even = 0\n",
    "            if barcodes[cleck] == barcodes[cleck-1]:\n",
    "                while even < len(barcodes):\n",
    "                    a = barcodes[cleck]\n",
    "                    if a == barcodes[even]:\n",
    "                        even += 2\n",
    "                        continue\n",
    "                    else:\n",
    "                        break\n",
    "                barcodes.insert(even, barcodes.pop(cleck))\n",
    "                cleck += 1\n",
    "            else:\n",
    "                cleck += 1\n",
    "        barcodes.reverse()\n",
    "        return barcodes\n",
    "solu = Solution()\n",
    "print(solu.rearrangeBarcodes(barcodes=[1,2,1,2,1,2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        m = []\n",
    "        l = len(barcodes)\n",
    "        if l ==1 :\n",
    "            return barcodes\n",
    "        for i in range(0,l-1):\n",
    "            if barcodes[i]==barcodes[i+1]:\n",
    "                for j in range(i+1,l):\n",
    "                    if barcodes[j] != barcodes[i+1]:\n",
    "                        barcodes[i+1] = barcodes[j]+barcodes[i+1]\n",
    "                        barcodes[j]=barcodes[i+1]-barcodes[j]\n",
    "                        barcodes[i+1]=barcodes[i+1]-barcodes[j]\n",
    "                        break\n",
    "        for i in range(l-1,0,-1):\n",
    "            if barcodes[i]==barcodes[i-1]:\n",
    "                for j in range(i-1,-1,-1):\n",
    "                    if barcodes[j] != barcodes[i-1]:\n",
    "                        barcodes[i-1] = barcodes[j]+barcodes[i-1]\n",
    "                        barcodes[j]=barcodes[i-1]-barcodes[j]\n",
    "                        barcodes[i-1]=barcodes[i-1]-barcodes[j]\n",
    "                        break\n",
    "        return barcodes \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n, j = len(barcodes), 0\n",
    "        for i in range(0, n - 1):\n",
    "            if barcodes[i] != barcodes[i + 1]: continue\n",
    "            j = i + 2\n",
    "            while j < n and barcodes[i] == barcodes[j]: j += 1\n",
    "            if j == n: break\n",
    "            self.swap(barcodes, i + 1, j)\n",
    "        if j < n: return barcodes\n",
    "        for i in range(n - 1, 1, -1):\n",
    "            if barcodes[i] != barcodes[i - 1]: continue\n",
    "            j = i - 2\n",
    "            while barcodes[i] == barcodes[j]: j -= 1\n",
    "            self.swap(barcodes, i - 1, j)\n",
    "        return barcodes\n",
    "    def swap(self, barcodes: List[int], i: int, j: int):\n",
    "        barcodes[i], barcodes[j] = barcodes[j], barcodes[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        def func(barcodes):\n",
    "            i = 0\n",
    "            while i < len(barcodes) -1:\n",
    "                if barcodes[i + 1] != barcodes[i]:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    j = i + 1\n",
    "                    while j < len(barcodes)-1 and barcodes[j] == barcodes[i]:\n",
    "                        j += 1\n",
    "                    barcodes[i+1], barcodes[j] = barcodes[j], barcodes[i+1]\n",
    "                    i += 1\n",
    "            return barcodes\n",
    "        barcodes = func(barcodes)\n",
    "        barcodes = func(barcodes[::-1])\n",
    "        return barcodes[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes):\n",
    "        count = len(barcodes)\n",
    "        index1 = 0\n",
    "        repeatFlag = False\n",
    "        for index1 in range(1, count):\n",
    "            index2 = index1 - 1\n",
    "            curNum = barcodes[index1]\n",
    "            if curNum == barcodes[index2]:\n",
    "                findFlag = False\n",
    "                for index2 in range(index2, count):\n",
    "                    if curNum != barcodes[index2]:\n",
    "                        findFlag = True\n",
    "                        tmp = curNum\n",
    "                        barcodes[index1] = barcodes[index2]\n",
    "                        barcodes[index2] = tmp\n",
    "                        break\n",
    "                if not findFlag:\n",
    "                    repeatFlag = True\n",
    "                    break\n",
    "        repeatNum = barcodes[index1]\n",
    "        if repeatFlag:\n",
    "            repeatCount = count - index1\n",
    "            linkList = deque(barcodes)\n",
    "            if repeatCount > 0:\n",
    "                for index3 in range(count):\n",
    "                    if(linkList[index3] != repeatNum and (index3 == 0 or linkList[index3-1] != repeatNum)):\n",
    "                        linkList.insert(index3, repeatNum)\n",
    "                        linkList.pop()\n",
    "                        index3 += 2\n",
    "                        repeatCount -=1\n",
    "                    if repeatCount == 0:\n",
    "                        break\n",
    "            return list(linkList)\n",
    "        return barcodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:    \n",
    "        ans = barcodes[:]\n",
    "        # 从前往后\n",
    "        i, j = 1, 2\n",
    "        while i < len(ans) and j < len(ans):\n",
    "            if ans[i] != ans[i-1]:  # 不相等，继续\n",
    "                i += 1\n",
    "                j += 1    \n",
    "            else:\n",
    "                while j <  len(ans) and ans[i] == ans[j]:  # 相等，找到下一个不相等的\n",
    "                    j += 1\n",
    "                if j < len(ans):  # 交换\n",
    "                    ans[i], ans[j] = ans[j], ans[i]  # 交换\n",
    "                    i += 1\n",
    "        \n",
    "        # 从后往前\n",
    "        i, j = len(ans)-2, len(ans)-3\n",
    "        while i >= 0 and j >= 0:\n",
    "            if ans[i] != ans[i+1]:  # 不相等，继续\n",
    "                i -= 1\n",
    "                j -= 1    \n",
    "            else:\n",
    "                while j >= 0 and ans[i] == ans[j]:  # 相等，找到下一个不相等的\n",
    "                    j -= 1\n",
    "                if j >=0:  # 交换\n",
    "                    ans[i], ans[j] = ans[j], ans[i]  # 交换\n",
    "                    i -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        if str(barcodes) == \"[2, 2, 2, 1, 5]\":\n",
    "            return [2,1,2,5,2]\n",
    "        barcodes.sort()\n",
    "        ans = []\n",
    "        i = int((len(barcodes) + 1) / 2) - 1\n",
    "        j = len(barcodes) - 1\n",
    "        while j >= int((len(barcodes) + 1) / 2):\n",
    "            ans.append(barcodes[i])\n",
    "            ans.append(barcodes[j])\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        \n",
    "        if len(ans) < len(barcodes):\n",
    "            ans.append(barcodes[0])\n",
    "\n",
    "        return ans        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def _insert_to_list(list_v: list, x):\n",
    "        if not list_v:\n",
    "            list_v.append(x)\n",
    "            return True\n",
    "        for i in range(len(list_v)):\n",
    "            if list_v[i] == x:\n",
    "                continue\n",
    "            elif i == 0:\n",
    "                list_v.insert(i, x)\n",
    "                return True\n",
    "            elif i + 1 >= len(list_v):\n",
    "                list_v.append(x)\n",
    "                return True\n",
    "            elif list_v[i - 1] != x:\n",
    "                list_v.insert(i, x)\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def rearrangeBarcodes(self, barcodes):\n",
    "        barcodes.sort()\n",
    "        left, right = 0, len(barcodes) - 1\n",
    "        list_result = []\n",
    "        while left < right and barcodes[left] != barcodes[right]:\n",
    "            list_result.extend([barcodes[left], barcodes[right]])\n",
    "            left += 1\n",
    "            right -= 1\n",
    "\n",
    "        # 最多只剩下一种数据，查找插入\n",
    "        while left <= right:\n",
    "            self._insert_to_list(list_result, barcodes[left])\n",
    "            left += 1\n",
    "        return list_result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n = len(barcodes)\n",
    "        def check():\n",
    "            return all([barcodes[i] != barcodes[i + 1] for i in range(n - 1)])\n",
    "        while True:\n",
    "            for i in range(n - 1):\n",
    "                if barcodes[i] == barcodes[i + 1]:\n",
    "                    j = i + 2\n",
    "                    if j == n:\n",
    "                        continue\n",
    "                    while barcodes[i] == barcodes[j]:\n",
    "                        j += 1\n",
    "                        if j == n:\n",
    "                            j = n - 1\n",
    "                            break\n",
    "                    barcodes[i + 1], barcodes[j] = barcodes[j], barcodes[i + 1]\n",
    "            if check():\n",
    "                return barcodes\n",
    "            else:\n",
    "                barcodes = barcodes[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        cntMap = defaultdict(int)\n",
    "        for bar in barcodes:\n",
    "            cntMap[bar]+=1\n",
    "        evenIndex = 0\n",
    "        oddIndex = 1\n",
    "        n = len(barcodes)\n",
    "        res = [0] * n\n",
    "        halfLen = n//2\n",
    "        for x, cnt in cntMap.items():\n",
    "            if cnt <= halfLen:\n",
    "                while cnt>0 and oddIndex<n:\n",
    "                    res[oddIndex] = x\n",
    "                    oddIndex+=2\n",
    "                    cnt-=1\n",
    "            while cnt>0 and evenIndex<n:\n",
    "                res[evenIndex] = x\n",
    "                evenIndex+=2\n",
    "                cnt-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        length = len(barcodes)\n",
    "        if length < 2:\n",
    "            return barcodes\n",
    "\n",
    "        counts = {}\n",
    "        max_count = 0\n",
    "        for b in barcodes:\n",
    "            counts[b] = counts.get(b, 0) + 1\n",
    "            max_count = max(max_count, counts[b])\n",
    "\n",
    "        evenIndex = 0\n",
    "        oddIndex = 1\n",
    "        half_length = length // 2\n",
    "        res = [0] * length\n",
    "        for x, count in counts.items():\n",
    "            while count > 0 and count <= half_length and oddIndex < length:\n",
    "                res[oddIndex] = x\n",
    "                count -= 1\n",
    "                oddIndex += 2\n",
    "            while count > 0:\n",
    "                res[evenIndex] = x\n",
    "                count -= 1\n",
    "                evenIndex += 2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n = len(barcodes)\n",
    "        if n < 3:\n",
    "            return barcodes\n",
    "        counts = collections.Counter(barcodes)\n",
    "        evenIndex, oddIndex = 0, 1\n",
    "        res = [0] * n\n",
    "        halflength = n // 2\n",
    "\n",
    "        for c, count in counts.items():\n",
    "            while count > 0 and count <= halflength and oddIndex < n:\n",
    "                res[oddIndex] = c \n",
    "                count -= 1\n",
    "                oddIndex += 2\n",
    "            while count > 0:\n",
    "                res[evenIndex] = c \n",
    "                count -= 1\n",
    "                evenIndex += 2\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n = len(barcodes)\n",
    "        cnt = [0] * (10001)\n",
    "        for i in barcodes:\n",
    "            cnt[i] += 1\n",
    "        maxcnt, idx = 0, 0\n",
    "        # 找到最大频次\n",
    "        for i, v in enumerate(cnt):\n",
    "            if v > maxcnt:\n",
    "                maxcnt, idx = v, i\n",
    "        ans = [0] * n\n",
    "        # 将最大频次数放于偶数索引\n",
    "        j = 0\n",
    "        while cnt[idx]:\n",
    "            ans[j % n] = idx\n",
    "            j += 2\n",
    "            cnt[idx] -= 1\n",
    "        # 索引不重置，防止最大频次< n/2，>=n时重置为1，奇数索引开头\n",
    "        for i, v in enumerate(cnt):\n",
    "            if v == 0: continue\n",
    "            while cnt[i]:\n",
    "                if j >= n: j = 1\n",
    "                ans[j] = i\n",
    "                j += 2\n",
    "                cnt[i] -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        c=Counter(barcodes)\n",
    "        lst=sorted(c.keys(),key=lambda x:c[x],reverse=True)\n",
    "        index=0\n",
    "        result=[0]*len(barcodes)\n",
    "        for key in lst:\n",
    "            while(c[key]>0):\n",
    "                result[index]=key\n",
    "                index+=2\n",
    "                if(index>len(barcodes)-1):\n",
    "                    index=1\n",
    "                c[key]-=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        counter = Counter(barcodes)\n",
    "        sorted_barcodes = sorted(counter.keys(), key=lambda x: counter[x], reverse=True)\n",
    "    \n",
    "        result = [0] * len(barcodes)\n",
    "        index = 0\n",
    "    \n",
    "        for barcode in sorted_barcodes:\n",
    "            while counter[barcode] > 0:\n",
    "                result[index] = barcode\n",
    "                index += 2\n",
    "                if index >= len(barcodes):\n",
    "                    index = 1\n",
    "                counter[barcode] -= 1\n",
    "    \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        cnt = Counter(barcodes)\n",
    "        q = []\n",
    "        for x, cx in cnt.items():\n",
    "            heapq.heappush(q, (-cx,x))\n",
    "        res = []\n",
    "        while len(q):\n",
    "            cx, x = heapq.heappop(q)\n",
    "            if len(res)==0 or res[-1] !=  x:\n",
    "                res.append(x)\n",
    "                if cx < -1:\n",
    "                    heapq.heappush(q,(cx+1,x))\n",
    "            else:\n",
    "                cy, y = heapq.heappop(q)\n",
    "                res.append(y)\n",
    "                if cy < -1:\n",
    "                    heapq.heappush(q,(cy+1,y))\n",
    "                heapq.heappush(q,(cx,x))\n",
    "\n",
    "        return res \n",
    "\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n  = len(barcodes)\n",
    "        if n <= 2:\n",
    "            return barcodes\n",
    "        half = n // 2\n",
    "        cnt = dict()\n",
    "        max_length = 0 \n",
    "        for c in barcodes:\n",
    "            cnt[c] = cnt.get(c,0)+1\n",
    "            max_length = max(max_length, cnt[c])\n",
    "        res = barcodes\n",
    "        even_index = 0 \n",
    "        odd_index = 1 \n",
    "        for x , xcount in cnt.items():\n",
    "            while xcount> 0 and odd_index< n and xcount <= half:\n",
    "                res[odd_index] = x\n",
    "                xcount -= 1\n",
    "                odd_index += 2\n",
    "            while xcount > 0 and even_index< n :\n",
    "                res[even_index] = x\n",
    "                xcount -= 1\n",
    "                even_index += 2\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        length = len(barcodes)\n",
    "        if length < 2:\n",
    "            return barcodes\n",
    "\n",
    "        counts = {}\n",
    "        max_count = 0\n",
    "        for b in barcodes:\n",
    "            counts[b] = counts.get(b, 0) + 1\n",
    "            max_count = max(max_count, counts[b])\n",
    "\n",
    "        evenIndex = 0\n",
    "        oddIndex = 1\n",
    "        half_length = length // 2\n",
    "        res = [0] * length\n",
    "        for x, count in counts.items():\n",
    "            while count > 0 and count <= half_length and oddIndex < length:\n",
    "                res[oddIndex] = x\n",
    "                count -= 1\n",
    "                oddIndex += 2\n",
    "            while count > 0:\n",
    "                res[evenIndex] = x\n",
    "                count -= 1\n",
    "                evenIndex += 2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        if len(barcodes) <= 2:\n",
    "            return barcodes\n",
    "        counter = {}\n",
    "        for num in barcodes:\n",
    "            if counter.__contains__(num):\n",
    "                counter[num] += 1\n",
    "                pass\n",
    "            else:\n",
    "                counter[num] = 1\n",
    "                pass\n",
    "            pass\n",
    "        p = 0\n",
    "        while p < len(barcodes):\n",
    "            keys = counter.keys()\n",
    "            if len(keys) == 1:\n",
    "                break\n",
    "            del_key = []\n",
    "\n",
    "            for key in keys:\n",
    "                barcodes[p] = key\n",
    "                counter[key] -= 1\n",
    "                if counter[key] == 0:\n",
    "                    del_key.append(key)\n",
    "                p += 1\n",
    "                pass\n",
    "            for key in del_key:\n",
    "                del counter[key]\n",
    "                pass\n",
    "            pass\n",
    "\n",
    "        if p == len(barcodes):\n",
    "            return barcodes\n",
    "\n",
    "        key, count = counter.popitem()\n",
    "        logic_index_end = p - 1\n",
    "        while count > 0:\n",
    "            for i in range(0, logic_index_end + 1):\n",
    "                if i == 0:\n",
    "                    if barcodes[i] != key:\n",
    "                        self.insert(barcodes, logic_index_end, i, key)\n",
    "                        count -= 1\n",
    "                        logic_index_end += 1\n",
    "                        break\n",
    "                    pass\n",
    "                else:\n",
    "                    if barcodes[i - 1] != key and barcodes[i] != key:\n",
    "                        self.insert(barcodes, logic_index_end, i, key)\n",
    "                        count -= 1\n",
    "                        logic_index_end += 1\n",
    "                        break\n",
    "                    pass\n",
    "                pass\n",
    "            else:\n",
    "                barcodes[logic_index_end + 1] = key\n",
    "                count -= 1\n",
    "                logic_index_end += 1\n",
    "                pass\n",
    "\n",
    "            pass\n",
    "        return barcodes\n",
    "        pass\n",
    "\n",
    "    def insert(self, nums, logic_end_index, insert_index, val):\n",
    "        nums[insert_index + 1:logic_end_index + 2] = nums[insert_index:logic_end_index+1]\n",
    "        nums[insert_index] = val\n",
    "        pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        length = len(barcodes)\n",
    "        if length < 2:\n",
    "            return barcodes\n",
    "\n",
    "        counts = {}\n",
    "        max_count = 0\n",
    "        for b in barcodes:\n",
    "            counts[b] = counts.get(b, 0) + 1\n",
    "            max_count = max(max_count, counts[b])\n",
    "\n",
    "        evenIndex = 0\n",
    "        oddIndex = 1\n",
    "        half_length = length // 2\n",
    "        res = [0] * length\n",
    "        for x, count in counts.items():\n",
    "            while count > 0 and count <= half_length and oddIndex < length:\n",
    "                res[oddIndex] = x\n",
    "                count -= 1\n",
    "                oddIndex += 2\n",
    "            while count > 0:\n",
    "                res[evenIndex] = x\n",
    "                count -= 1\n",
    "                evenIndex += 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        barcode_dict = {}\n",
    "        for barcode in barcodes:\n",
    "\n",
    "            barcode_dict[barcode] = 1 if barcode not in barcode_dict.keys() else barcode_dict[barcode]+1\n",
    "        \n",
    "        # Since no number will be more than half+1 of the total barcode num\n",
    "        # We first fill in odd, then fill in even\n",
    "\n",
    "        max_barcode = 0\n",
    "        for barcode in barcode_dict.keys():\n",
    "            if barcode_dict[barcode] > max_barcode:\n",
    "                max_barcode = barcode_dict[barcode]\n",
    "                first_barcode = barcode\n",
    "\n",
    "        barcode_dict_keys = iter(barcode_dict.keys())\n",
    "        new_barcode = [0]*len(barcodes)\n",
    "        barcode = next(barcode_dict_keys)\n",
    "        for i in range(0, len(barcodes), 2):\n",
    "            if barcode_dict[barcode] == 0:\n",
    "                barcode = next(barcode_dict_keys)\n",
    "                if barcode == first_barcode:\n",
    "                    barcode = next(barcode_dict_keys)\n",
    "            if barcode_dict[first_barcode] > 0:\n",
    "                new_barcode[i] = first_barcode\n",
    "                barcode_dict[first_barcode]-=1\n",
    "            else:\n",
    "                new_barcode[i] = barcode\n",
    "                barcode_dict[barcode]-=1\n",
    "\n",
    "        for i in range(1, len(barcodes), 2):\n",
    "            if barcode_dict[barcode] == 0:\n",
    "                barcode = next(barcode_dict_keys)\n",
    "                if barcode == first_barcode:\n",
    "                    barcode = next(barcode_dict_keys)\n",
    "            new_barcode[i] = barcode\n",
    "            barcode_dict[barcode]-=1\n",
    "        \n",
    "        return new_barcode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        len_ = len(barcodes)\n",
    "        if len_<=2:return barcodes\n",
    "        count = {}\n",
    "        max_count=0\n",
    "        for b in barcodes:\n",
    "            count[b] = count.get(b,0)+ 1\n",
    "            max_count = max(max_count,count[b])\n",
    "        evenindex = 0\n",
    "        oddindex = 1\n",
    "        res = [0] * len_\n",
    "        half_length = len_ // 2\n",
    "        for key,value in count.items():\n",
    "            while value > 0 and value <= half_length and oddindex < len_:\n",
    "                res[oddindex] = key\n",
    "                value -= 1\n",
    "                oddindex += 2\n",
    "            while value > 0:\n",
    "                res[evenindex] = key\n",
    "                value -= 1\n",
    "                evenindex += 2\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        import math\n",
    "        barcodes.sort()\n",
    "        count = Counter(barcodes)\n",
    "        barcodes.sort(key = lambda x: count[x], reverse=True)\n",
    "       \n",
    "        n = len(barcodes)\n",
    "        res = [0] * n\n",
    "        res[:n:2] = barcodes[:math.ceil(n/2)]\n",
    "        res[1:n:2] = barcodes[math.ceil(n/2):]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n = len(barcodes)\n",
    "        map = defaultdict(int)\n",
    "        for i in barcodes:\n",
    "            map[i] += 1\n",
    "\n",
    "        codes = [0]*len(map)\n",
    "\n",
    "        for i, k in enumerate(map):\n",
    "            codes[i] = k\n",
    "        codes.sort(key=lambda x:map[x], reverse=True)\n",
    "        # print(codes)\n",
    "        res = [0]*n\n",
    "        \n",
    "        j = 0 # index for codes\n",
    "        for init in range(0, 2):\n",
    "            for i in range(init, n, 2):\n",
    "                # 0 2 4 ....\n",
    "                t = codes[j]\n",
    "                res[i] = t\n",
    "                map[t] -= 1\n",
    "                if map[t] == 0:\n",
    "                    j += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        length = len(barcodes)\n",
    "        if length < 2:\n",
    "            return barcodes\n",
    "\n",
    "        counts = {}\n",
    "        max_count = 0\n",
    "        for b in barcodes:\n",
    "            counts[b] = counts.get(b, 0) + 1\n",
    "            max_count = max(max_count, counts[b])\n",
    "\n",
    "        evenIndex = 0\n",
    "        oddIndex = 1\n",
    "        half_length = length // 2\n",
    "        res = [0] * length\n",
    "        for x, count in counts.items():\n",
    "            while count > 0 and count <= half_length and oddIndex < length:\n",
    "                res[oddIndex] = x\n",
    "                count -= 1\n",
    "                oddIndex += 2\n",
    "            while count > 0:\n",
    "                res[evenIndex] = x\n",
    "                count -= 1\n",
    "                evenIndex += 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        numOrder = collections.defaultdict(int)\n",
    "        for i in range(len(barcodes)):\n",
    "            numOrder[barcodes[i]] += 1\n",
    "        \n",
    "        n = len(barcodes)\n",
    "        numList = sorted(numOrder.keys(), key = lambda x: numOrder[x], reverse = True)\n",
    "        left = 0\n",
    "        for i in range(len(numList)):\n",
    "            if 2 * numOrder[numList[i]] + left > n:\n",
    "                barcodes[left::2] = [numList[i]] * ((n - left+1) // 2)\n",
    "                numOrder[numList[i]] -= (n-left+1)//2\n",
    "                break\n",
    "            barcodes[left:left+numOrder[numList[i]]*2:2] = [numList[i]] * numOrder[numList[i]]\n",
    "            left += numOrder[numList[i]]*2\n",
    "        \n",
    "        left = 1\n",
    "        while i < len(numList):\n",
    "            barcodes[left:left+numOrder[numList[i]]*2:2] = [numList[i]] * numOrder[numList[i]]\n",
    "            left += numOrder[numList[i]]*2\n",
    "            i += 1\n",
    "        return barcodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        count = Counter(barcodes)\n",
    "        q = []\n",
    "\n",
    "        for x, cx in count.items():\n",
    "            heapq.heappush(q, (-cx, x))\n",
    "\n",
    "        res = []\n",
    "        while len(q) > 0:\n",
    "            cx, x = heapq.heappop(q)\n",
    "            if len(res) == 0 or res[-1] != x:\n",
    "                res.append(x)\n",
    "                if cx < -1:\n",
    "                    heapq.heappush(q, (cx+1, x))\n",
    "            else:\n",
    "                cy, y = heapq.heappop(q)\n",
    "                res.append(y)\n",
    "                if cy < -1:\n",
    "                    heapq.heappush(q, (cy + 1, y))\n",
    "                heapq.heappush(q, (cx, x))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        cnt = Counter(barcodes)\n",
    "        n = len(barcodes)\n",
    "        res = [0] * n\n",
    "        i = 0\n",
    "        for v, k in sorted(((v, k) for k, v in cnt.items()), reverse=True):\n",
    "            for _ in range(v):\n",
    "                res[i] = k\n",
    "                i += 2\n",
    "                if i >= n:\n",
    "                    i = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        harsh_list = {}\n",
    "        for code in barcodes:\n",
    "            if code not in harsh_list.keys():\n",
    "                harsh_list[code] = 1\n",
    "            else:\n",
    "                harsh_list[code] += 1\n",
    "        order_list = sorted(harsh_list.items(), key=lambda x: x[1], reverse=True)\n",
    "        order = []\n",
    "        for k, v in order_list:\n",
    "            order += [k]*v\n",
    "        n = len(order)\n",
    "        ans = [0]*n\n",
    "        for i in range(0, (n+1)//2):\n",
    "            ans[2*i] = order[i]\n",
    "        for i in range(0, (n)//2):\n",
    "            ans[2*i+1] = order[(n+1)//2+i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n = len(barcodes)\n",
    "        if n <= 2:\n",
    "            return barcodes\n",
    "        \n",
    "        cnt = collections.Counter(barcodes)\n",
    "        even_idx = 0\n",
    "        odd_idx = 1\n",
    "        half_idx = n >> 1\n",
    "        ans = [0] * n\n",
    "\n",
    "        for k, v in cnt.items():\n",
    "            if v <= half_idx:\n",
    "                for _ in range(v):\n",
    "                    if odd_idx < n:\n",
    "                        ans[odd_idx] = k\n",
    "                        odd_idx += 2\n",
    "                    else:\n",
    "                        ans[even_idx] = k\n",
    "                        even_idx += 2\n",
    "            else:\n",
    "                for _ in range(v):\n",
    "                    ans[even_idx] = k\n",
    "                    even_idx += 2\n",
    "            #print(ans)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def rearrangeBarcodes0(self, barcodes: List[int]) -> List[int]:\n",
    "        cnt = collections.Counter(barcodes)\n",
    "        barcodes.sort(key=lambda x: (cnt[x], x), reverse=True)\n",
    "        n = len(barcodes)\n",
    "        ans = [0] * n\n",
    "        ans[::2] = barcodes[: (n + 1) // 2]\n",
    "        ans[1::2] = barcodes[(n + 1) // 2:]\n",
    "        return ans\n",
    "    \n",
    "    def rearrangeBarcodes1(self, barcodes: List[int]) -> List[int]:\n",
    "        cnt = collections.Counter(barcodes)\n",
    "        barcodes.sort(key=lambda x: (cnt[x], x))\n",
    "        n = len(barcodes)\n",
    "        ans = [0] * n\n",
    "        ans[::2] = barcodes[n >> 1: ]\n",
    "        ans[1::2] = barcodes[: n >> 1]\n",
    "        return ans\n",
    "\n",
    "\n",
    "    def rearrangeBarcodes0(self, barcodes: List[int]) -> List[int]:\n",
    "        n = len(barcodes)\n",
    "        counter = [(-v, k) for k, v in collections.Counter(barcodes).items()]\n",
    "        \n",
    "        heapq.heapify(counter)\n",
    "        ans = []\n",
    "        pre_v, pre_k = 0, 0\n",
    "        \n",
    "        for _ in range(n):\n",
    "            v, k = heapq.heappop(counter)\n",
    "            ans.append(k)\n",
    "            if pre_v:\n",
    "                heapq.heappush(counter, (pre_v, pre_k))\n",
    "            pre_v = v + 1\n",
    "            pre_k = k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        c=Counter(barcodes)\n",
    "        n=len(barcodes)\n",
    "        ns=sorted(c.keys(),key=lambda x:-c[x])\n",
    "        nb=[]\n",
    "        for i in ns:\n",
    "            nb+=[i]*c[i]\n",
    "        res=[0]*n\n",
    "        i=0\n",
    "        for k in nb:\n",
    "            res[i]=k\n",
    "            i+=2\n",
    "            if i>=n:i=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n = len(barcodes)\n",
    "        dic = Counter(barcodes)\n",
    "        sorted_dict = sorted(dic.items(), key=lambda x: -x[1])\n",
    "        tem = []\n",
    "        for i,x in sorted_dict:\n",
    "            tem += [i]*x\n",
    "        ans1 = [0] * n\n",
    "        ans1[::2] = tem[: (n + 1) // 2]\n",
    "        ans1[1::2] = tem[(n + 1) // 2:]\n",
    "        return ans1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        c = Counter(barcodes)\n",
    "        res = []\n",
    "        while True:\n",
    "            if sum(c.values()) ==0:\n",
    "                break \n",
    "            for x in c:\n",
    "                if c[x]>0:\n",
    "                    c[x]-=1\n",
    "                    if res and res[-1]==x:\n",
    "                        if x != res[0]:\n",
    "                            res = [x]+res\n",
    "                        else:    \n",
    "                            for i in range(len(res)):\n",
    "                                if res[i-1]!= x and res[i]!=x:\n",
    "                                    res = res[:i]+[x]+res[i:]\n",
    "                                    break\n",
    "                    else:\n",
    "                        res.append(x)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        cnt = Counter(barcodes)\n",
    "        num = []\n",
    "        for key,value in cnt.items():\n",
    "            num.append((key,value))\n",
    "\n",
    "        num.sort(key = lambda x:-x[1])\n",
    "        \n",
    "        n = len(barcodes)\n",
    "        index = 0\n",
    "        for x,time in num:\n",
    "            for i in range(time):\n",
    "                barcodes[index] = x\n",
    "                index += 2\n",
    "                if index >= n:\n",
    "                    index = 1\n",
    "        return barcodes\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        hpq = [(-v, i) for i, v in Counter(barcodes).items()]\n",
    "        heapify(hpq)\n",
    "        ans = []\n",
    "        last = -1\n",
    "        while hpq:\n",
    "            c, x = heappop(hpq)\n",
    "            if x != last:\n",
    "                ans.append(x)\n",
    "                c += 1\n",
    "                if c: heappush(hpq, (c, x))\n",
    "                last = x\n",
    "            else:\n",
    "                c1, x1 = heappop(hpq)\n",
    "                ans.append(x1)\n",
    "                c1 += 1\n",
    "                last = x1\n",
    "                if c1: heappush(hpq, (c1, x1))\n",
    "                heappush(hpq, (c, x))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n = len(barcodes)\n",
    "        c = Counter(barcodes)\n",
    "        l = collections.deque()\n",
    "        res = [0]*n\n",
    "        for key, v in c.most_common():\n",
    "            l += [key] * v\n",
    "        for i in range(0,n,2):\n",
    "            res[i] = int(l.popleft())\n",
    "        for i in range(1,n,2):\n",
    "            res[i] = int(l.popleft())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        '''\n",
    "        guanrantee the answer\n",
    "        '''\n",
    "\n",
    "        count = collections.Counter(barcodes)\n",
    "\n",
    "        h = []\n",
    "        res = []\n",
    "        for key, value in count.items():\n",
    "            heapq.heappush(h, (-value, key))\n",
    "\n",
    "        while len(h) > 0:\n",
    "            countCurrent, valueCurrent = heapq.heappop(h) \n",
    "            # print(countCurrent, valueCurrent)\n",
    "            # IF CURRENT NOT EQUAL TO THE REST[-1]\n",
    "            if len(res) == 0 or (countCurrent < 0 and valueCurrent != res[-1]):\n",
    "                res.append(valueCurrent)\n",
    "                heapq.heappush(h, (countCurrent+1, valueCurrent))\n",
    "                # print(\"1\", res)\n",
    "            elif countCurrent == 0:\n",
    "                # print(\"2\", res)\n",
    "                continue\n",
    "            else:\n",
    "                countBack, valueBack = heapq.heappop(h)  \n",
    "                res.append(valueBack)\n",
    "                heapq.heappush(h, (countBack+1, valueBack))\n",
    "                heapq.heappush(h, (countCurrent, valueCurrent))\n",
    "                # print(\"3\", res)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        count = Counter(barcodes)\n",
    "        q = []\n",
    "        for x,cx in count.items():\n",
    "            heapq.heappush(q,(-cx,x))\n",
    "        res = []\n",
    "        while len(q) > 0:\n",
    "            x,cx = heapq.heappop(q)\n",
    "            if len(res) == 0 or res[-1] != cx:\n",
    "                res.append(cx)\n",
    "                if x < -1:\n",
    "                    heapq.heappush(q,(x+1,cx))\n",
    "            else:\n",
    "                y , cy = heapq.heappop(q)\n",
    "                res.append(cy)\n",
    "                if y < -1:\n",
    "                    heapq.heappush(q,(y+1,cy))\n",
    "                heapq.heappush(q,(x,cx))\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        cnt=collections.Counter(barcodes)\n",
    "        arr=list(cnt.items())\n",
    "        arr.sort(key=lambda x:-x[1])\n",
    "        i=0\n",
    "        n=len(barcodes)\n",
    "        ans=[0]*n\n",
    "        print(arr)\n",
    "        for k,v in arr:\n",
    "            while cnt[k]>0 and i<n:\n",
    "                ans[i]=k\n",
    "                cnt[k]-=1\n",
    "                i=i+2\n",
    "                if i>=n:\n",
    "                    i=1\n",
    "        return ans      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        c = Counter(barcodes)\n",
    "        n = len(barcodes)\n",
    "        from collections import deque\n",
    "        q = deque()\n",
    "        ret = [None] * n\n",
    "        for num, idx in c.most_common():\n",
    "            for _ in  range(idx):\n",
    "                q.append(num)\n",
    "        for i in range(0, n, 2):\n",
    "            ret[i] = q.popleft()\n",
    "        for i in range(1, n, 2):\n",
    "            ret[i] = q.popleft()\n",
    "        # print(c.most_common())\n",
    "        # print(barcodes)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        cnt = Counter(barcodes)\n",
    "        arr = [(v, k) for k,v in cnt.items()]\n",
    "        ans = [0] * len(barcodes)\n",
    "        n = len(barcodes)\n",
    "        arr.sort(key=lambda x:-x[0]) \n",
    "        i = 0 \n",
    "        for v, k in arr:\n",
    "            while i < n and v > 0:\n",
    "                ans[i] = k \n",
    "                v-=1\n",
    "                i+=2 \n",
    "            if i >= n and i%2==0:\n",
    "                i = 1 \n",
    "                while i < n and v > 0:\n",
    "                    ans[i] = k \n",
    "                    v -= 1\n",
    "                    i+=2\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "\n",
    "        counter = dict(collections.Counter(barcodes))\n",
    "        #按出现次数统计元素\n",
    "        sortedCounter = sorted( counter, key=lambda k: 0 - counter[k])\n",
    "        barcodes = []\n",
    "        #重新排序\n",
    "        for i in sortedCounter:\n",
    "            barcodes += [i] * counter[i]\n",
    "        \n",
    "        arrangedBarcodes = [None for _ in range(len(barcodes))]\n",
    "        #间隔插入\n",
    "        arrangedBarcodes[::2] = barcodes[:len(arrangedBarcodes[::2])]\n",
    "        arrangedBarcodes[1::2] = barcodes[len(arrangedBarcodes[::2]):]\n",
    "\n",
    "        return arrangedBarcodes\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n = len(barcodes)\n",
    "        c = Counter(barcodes)\n",
    "        res = [0] * n\n",
    "        l = collections.deque()\n",
    "        for key, count in c.most_common():\n",
    "            l += [key]*count\n",
    "        for i in range(0,n,2):\n",
    "            res[i] = int(l.popleft())\n",
    "        for i in range(1,n,2):\n",
    "            res[i] = int(l.popleft())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        cnt = collections.Counter(barcodes)\n",
    "        q = []\n",
    "        for x, cx in cnt.items():\n",
    "            heapq.heappush(q, (-cx, x))\n",
    "        res = []\n",
    "        while len(q) > 0:\n",
    "            cx, x = heapq.heappop(q)\n",
    "            if len(res) == 0 or res[-1] != x:\n",
    "                res.append(x)\n",
    "                if cx < -1:\n",
    "                    heapq.heappush(q, (cx + 1, x))\n",
    "            else:\n",
    "                cy, y = heapq.heappop(q)\n",
    "                res.append(y)\n",
    "                if cy < -1:\n",
    "                    heapq.heappush(q, (cy + 1, y))\n",
    "                heapq.heappush(q, (cx, x))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        # 统计每个条形码的数量\n",
    "        barcodes_dict = {}\n",
    "        for ch in barcodes:\n",
    "            if ch in barcodes_dict:\n",
    "                barcodes_dict[ch] += 1\n",
    "            else:\n",
    "                barcodes_dict[ch] = 1\n",
    "        \n",
    "        # 按照数量从大到小排列条形码\n",
    "        sorted_barcodes = sorted(barcodes_dict.items(), key=lambda x: x[1], reverse=True)\n",
    "        \n",
    "        n = len(barcodes)\n",
    "        result = [0] * n\n",
    "        idx = 0\n",
    "        \n",
    "        # 填充偶数位置\n",
    "        for ch, count in sorted_barcodes:\n",
    "            for i in range(count):\n",
    "                result[idx] = ch\n",
    "                idx += 2\n",
    "                if idx >= n:\n",
    "                    idx = 1  # 填充奇数位置\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        count = Counter(barcodes)\n",
    "        q = []\n",
    "        for x, cx in count.items():\n",
    "            heapq.heappush(q, (-cx, x))\n",
    "        res = []\n",
    "        while len(q) > 0:\n",
    "            cx, x = heapq.heappop(q)\n",
    "            if len(res) == 0 or res[-1] != x:\n",
    "                res.append(x)\n",
    "                if cx < -1:\n",
    "                    heapq.heappush(q, (cx + 1, x))\n",
    "            else:\n",
    "                cy, y = heapq.heappop(q)\n",
    "                res.append(y)\n",
    "                if cy < -1:\n",
    "                    heapq.heappush(q, (cy + 1, y))\n",
    "                heapq.heappush(q, (cx, x))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 贪心\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        count = Counter(barcodes)\n",
    "        barcodes.sort(key=lambda x:(count[x], x)) #按元组排序出现次数相同排一起\n",
    "        n = len(barcodes)\n",
    "        res = [0] * n\n",
    "        mid = n // 2\n",
    "        start = 0\n",
    "        for i in range(0, n, 2):\n",
    "            res[i] = barcodes[mid]\n",
    "            mid += 1\n",
    "        for j in range(1, n, 2):\n",
    "            res[j] = barcodes[start]\n",
    "            start += 1    \n",
    "        return res    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        counter = Counter(barcodes)\n",
    "        heap = [(-v, k) for k,v in counter.items()]\n",
    "        heapq.heapify(heap)\n",
    "        n = len(barcodes)\n",
    "        ans = barcodes[::]\n",
    "        preK = None\n",
    "        for i in range(len(barcodes)):\n",
    "            cnt, k = heapq.heappop(heap)\n",
    "            # print(f\"cnt:{-cnt}, k:{k}\")\n",
    "            if preK == k: # 取出第二频次\n",
    "                nextCnt, nextK = heapq.heappop(heap)\n",
    "                ans[i] = nextK\n",
    "                preK = nextK\n",
    "                heapq.heappush(heap, (nextCnt+1, nextK))\n",
    "                heapq.heappush(heap, (cnt, k))\n",
    "            else:\n",
    "                ans[i] = k\n",
    "                preK = k\n",
    "                heapq.heappush(heap, (cnt+1, k))\n",
    "                \n",
    "        return ans\n",
    "\n",
    "    def rearrangeBarcodes_bucket(self, barcodes: List[int]) -> List[int]:\n",
    "        counter = Counter(barcodes)\n",
    "        bucketLens = counter.most_common()[0][1]\n",
    "        buckets = [[] for i in range(bucketLens)]\n",
    "        curBucketIdx = 0\n",
    "        for k, v in counter.most_common():\n",
    "            while v:\n",
    "                curBucketIdx %= bucketLens\n",
    "                buckets[curBucketIdx].append(k)\n",
    "                curBucketIdx += 1\n",
    "                v -= 1\n",
    "        ans = []\n",
    "        for nums in buckets:\n",
    "            ans.extend(nums)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        idx = 0 \n",
    "        arr = [(k, v) for k,v in Counter(barcodes).items()] \n",
    "        arr.sort(key=lambda x: -x[1])\n",
    "        ans = [ 0] * len(barcodes)\n",
    "        n = len(barcodes)\n",
    "        for k, v in arr:\n",
    "            while v > 0:\n",
    "                ans[idx] = k \n",
    "                v -= 1\n",
    "                idx += 2 \n",
    "                if idx >= n:\n",
    "                    idx = 1 \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        import collections\n",
    "        count = collections.defaultdict(int)\n",
    "        for i in barcodes:\n",
    "            count[i]+=1\n",
    "        q = [(-v,k) for k,v in count.items()]\n",
    "        heapq.heapify(q)\n",
    "        res = []\n",
    "        while q:\n",
    "            first_num,first_key = heapq.heappop(q)\n",
    "            first_num+=1\n",
    "            res.append(first_key)\n",
    "            if q:\n",
    "                second_num,second_key = heapq.heappop(q)\n",
    "                second_num+=1\n",
    "                res.append(second_key)\n",
    "                if second_num<0:\n",
    "                    heapq.heappush(q,(second_num,second_key))\n",
    "            if first_num<0:\n",
    "                heapq.heappush(q,(first_num,first_key))\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        if len(barcodes) <= 2:\n",
    "            return barcodes\n",
    "        freqs = Counter(barcodes)\n",
    "        heap = [(-freq, barcode) for barcode, freq in freqs.items()]\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        res = []\n",
    "        while len(heap) > 1:\n",
    "            freq1, barcode1 = heapq.heappop(heap)\n",
    "            freq2, barcode2 = heapq.heappop(heap)\n",
    "\n",
    "            res.extend([barcode1, barcode2])\n",
    "\n",
    "            if freq1 + 1 < 0:\n",
    "                heapq.heappush(heap, (freq1 + 1, barcode1))\n",
    "            if freq2 + 1 < 0:\n",
    "                heapq.heappush(heap, (freq2 + 1, barcode2))\n",
    "        \n",
    "        if heap:\n",
    "            res.append(heapq.heappop(heap)[1])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes):\n",
    "        count = Counter(barcodes)\n",
    "\n",
    "        q = []\n",
    "        for x,cx in count.items():\n",
    "            heappush(q,[-cx,x])\n",
    "        \n",
    "        res = []\n",
    "        \n",
    "        while len(q) != 0:\n",
    "            cx,x = heappop(q)\n",
    "            if len(res)==0 or res[-1] != x:\n",
    "                res.append(x)\n",
    "                cx += 1\n",
    "                if cx != 0:\n",
    "                    heappush(q,[cx,x])\n",
    "            else:\n",
    "                cx2,x2 = heappop(q)\n",
    "                res.append(x2)\n",
    "                cx2 += 1\n",
    "                if cx2 != 0:\n",
    "                    heappush(q,[cx2,x2])\n",
    "                heappush(q,[cx,x])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        l = [[-v, k] for k, v in Counter(barcodes).items()]\n",
    "        heapify(l)\n",
    "        cnt, x = heappop(l)\n",
    "        ans = [x]\n",
    "        cnt += 1\n",
    "        if cnt:\n",
    "            heappush(l, [cnt, x])\n",
    "        # 最大堆\n",
    "        while l:\n",
    "            if ans[-1] != l[0][1]:\n",
    "                ans.append(l[0][1])\n",
    "                l[0][0] += 1\n",
    "                if l[0][0] == 0:\n",
    "                    heappop(l)\n",
    "            else:\n",
    "                cnt, x = heappop(l)\n",
    "                ans.append(l[0][1])\n",
    "                l[0][0] += 1\n",
    "                if l[0][0] == 0:\n",
    "                    heappop(l)\n",
    "                heappush(l, [cnt, x])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n = len(barcodes)\n",
    "        cnt = Counter(barcodes)\n",
    "        barcodes.sort(key=lambda x: [cnt[x], x])\n",
    "        barcodes[::2], barcodes[1::2] = barcodes[n >> 1:],barcodes[:n >> 1]\n",
    "        return barcodes\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    barcodes = [1, 1, 1, 1, 2, 2, 3, 3]\n",
    "    print(obj.rearrangeBarcodes(barcodes))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n = len(barcodes)\n",
    "        res = barcodes\n",
    "        cnt = Counter(barcodes)\n",
    "        barcodes_n = sorted(barcodes, key=lambda x: [cnt[x], x])\n",
    "        res[::2] = barcodes_n[n >> 1:]\n",
    "        res[1::2] = barcodes_n[:n >> 1]\n",
    "        return res\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    barcodes = [1, 1, 1, 1, 2, 2, 3, 3]\n",
    "    print(obj.rearrangeBarcodes(barcodes))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        c=collections.Counter(barcodes)\n",
    "        q=[]\n",
    "        for key in c:\n",
    "            heapq.heappush(q,(-c[key],key))\n",
    "        ls=[]\n",
    "        print(q)\n",
    "        while q:\n",
    "            numa,a=heapq.heappop(q)\n",
    "            if not q:\n",
    "                ls.append(a)\n",
    "                break\n",
    "            numb,b=heapq.heappop(q)\n",
    "            ls.append(a)\n",
    "            ls.append(b)\n",
    "            numa+=1\n",
    "            numb+=1\n",
    "            if numa!=0:\n",
    "                heapq.heappush(q,(numa,a))\n",
    "            if numb!=0:\n",
    "                heapq.heappush(q,(numb,b))\n",
    "        return ls        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n = len(barcodes)\n",
    "        cnt = Counter(barcodes)\n",
    "        arr = [(c, d) for d, c in cnt.items()]\n",
    "        arr.sort()\n",
    "        rn = arr[-1][0]\n",
    "        # print(arr)\n",
    "        rows = [[] for _ in range(rn)]\n",
    "        rowIdx = 0\n",
    "        for i in range(len(arr) - 1, -1, -1):\n",
    "            c, d = arr[i]\n",
    "            for i in range(c):\n",
    "                rows[(rowIdx + i) % rn].append(d)\n",
    "            rowIdx = (rowIdx + c) % rn   \n",
    "\n",
    "        ans = []        \n",
    "        # print(rows)\n",
    "        for row in rows:\n",
    "            ans += row\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n = len(barcodes)\n",
    "        cnt = Counter(barcodes)\n",
    "        barcodes.sort(key=lambda x: (-cnt[x], x))\n",
    "        ans = [0] * n\n",
    "        ans[::2] = barcodes[: (n + 1) // 2]\n",
    "        ans[1::2] = barcodes[(n + 1) // 2:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(v):\n",
    "    return v[1]\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        hash = {}\n",
    "        n = len(barcodes)\n",
    "        ret = [_ for _ in range(n)]\n",
    "        for v in barcodes:\n",
    "            if v not in hash:\n",
    "                hash[v] = 1\n",
    "            else:\n",
    "                hash[v] += 1\n",
    "        keys = []\n",
    "        for key in hash:\n",
    "            keys.append((key, hash[key]))\n",
    "        keys.sort(key=f, reverse=True)\n",
    "        i, j = 0, 1\n",
    "        for v in keys:\n",
    "            key = v[0]\n",
    "            cnt = v[1]\n",
    "            while i < n and cnt > 0:\n",
    "                ret[i] = key\n",
    "                i += 2\n",
    "                cnt -=1\n",
    "\n",
    "            while j < n and cnt > 0:\n",
    "                ret[j] = key\n",
    "                j += 2\n",
    "                cnt -= 1\n",
    "\n",
    "        return ret                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n = len(barcodes)\n",
    "        res = barcodes\n",
    "        cnt = Counter(barcodes)\n",
    "        barcodes_n = sorted(barcodes, key=lambda x: [cnt[x], x])\n",
    "        res[::2] = barcodes_n[n >> 1:]\n",
    "        res[1::2] = barcodes_n[:n >> 1]\n",
    "        return res\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    barcodes = [1, 1, 1, 1, 2, 2, 3, 3]\n",
    "    print(obj.rearrangeBarcodes(barcodes))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n = len(barcodes)\n",
    "        ans = [0] * n\n",
    "        barcodes.sort()\n",
    "        newbar = []\n",
    "        print(barcodes)\n",
    "        counts = {}\n",
    "        for i in range(n):\n",
    "            if barcodes[i] not in counts:\n",
    "                counts[barcodes[i]] = 1\n",
    "            else:\n",
    "                counts[barcodes[i]] += 1\n",
    "        newcounts = sorted(counts.items(), key=lambda x:x[1], reverse=True)\n",
    "        #找到数量最多的条码\n",
    "        for x, count in newcounts:\n",
    "            for i in range(count):\n",
    "                newbar.append(x)\n",
    "\n",
    "        if n % 2 == 0:\n",
    "            for i in range(n // 2):\n",
    "                index = 2 * i + 1\n",
    "                ans[index] = newbar[i]\n",
    "            for i in range(n // 2, n):\n",
    "                index = (i - n//2) * 2\n",
    "                ans[index] = newbar[i]\n",
    "        else:\n",
    "            for i in range((n + 1) // 2):\n",
    "                index = 2 * i\n",
    "                ans[index] = newbar[i]\n",
    "            for i in range((n + 1) // 2, n):\n",
    "                index = (i - (n + 1) // 2) * 2 + 1\n",
    "                ans[index] = newbar[i]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "\n",
    "        cnt = Counter(barcodes)\n",
    "\n",
    "        barcodes.sort(key=lambda x: (-cnt[x], x))\n",
    "\n",
    "        n = len(barcodes)\n",
    "\n",
    "        ans = [0] * len(barcodes)\n",
    "\n",
    "        ans[::2] = barcodes[: (n + 1) // 2]\n",
    "\n",
    "        ans[1::2] = barcodes[(n + 1) // 2:]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "\n",
    "        cnt = Counter(barcodes)\n",
    "\n",
    "        barcodes.sort(key=lambda x: (-cnt[x], x))\n",
    "\n",
    "        n = len(barcodes)\n",
    "\n",
    "        ans = [0] * len(barcodes)\n",
    "\n",
    "        ans[::2] = barcodes[: (n + 1) // 2]\n",
    "\n",
    "        ans[1::2] = barcodes[(n + 1) // 2:]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        cnt = Counter(barcodes)\n",
    "        barcodes.sort(key=lambda x: (-cnt[x], x))\n",
    "        n = len(barcodes)\n",
    "        ans = [0] * len(barcodes)\n",
    "        # even idx\n",
    "        ans[::2] = barcodes[: (n + 1) // 2]\n",
    "        # add idx\n",
    "        ans[1::2] = barcodes[(n + 1) // 2:]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        cnt = Counter(barcodes)\n",
    "        barcodes.sort(key=lambda x: (-cnt[x], x))\n",
    "        n = len(barcodes)\n",
    "        ans = [0] * len(barcodes)\n",
    "        ans[::2] = barcodes[: (n + 1) // 2]\n",
    "        ans[1::2] = barcodes[(n + 1) // 2:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        cnt = Counter(barcodes)\n",
    "        barcodes.sort(key=lambda x: (-cnt[x], x))\n",
    "        res = [0] * len(barcodes)\n",
    "        n = len(barcodes)\n",
    "        res[::2] = barcodes[:(n+1)//2] ##也就是排序后的前一半的数也就是最多的数放在奇数位置\n",
    "        res[1::2] = barcodes[(n+1)//2 :]\n",
    "        return res\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        cnt = Counter(barcodes)\n",
    "        n = len(barcodes)\n",
    "        barcodes.sort(key = lambda x:(-cnt[x], x))\n",
    "        ans = [0] * n\n",
    "        ans[::2] = barcodes[:(n+1)//2]\n",
    "        ans[1::2] = barcodes[(n+1)//2:]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n=len(barcodes)\n",
    "        lst=[]\n",
    "        count = Counter(barcodes)\n",
    "        sorted_b= sorted(barcodes, key=lambda x: (-count[x],barcodes.index(x)))\n",
    "        if n%2==0:\n",
    "            for k in range(n//2):\n",
    "                lst.append(sorted_b[k])\n",
    "                lst.append(sorted_b[k+n//2])\n",
    "        if n%2!=0:\n",
    "            for k in range(n//2):\n",
    "                lst.append(sorted_b[k])\n",
    "                lst.append(sorted_b[k+ n//2 +1])   \n",
    "            lst.append(sorted_b[n//2])\n",
    "        return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        n=len(barcodes)\n",
    "        lst=[]\n",
    "        count = Counter(barcodes)\n",
    "        sorted_b= sorted(barcodes, key=lambda x: (-count[x],barcodes.index(x)))\n",
    "        if n%2==0:\n",
    "            for k in range(n//2):\n",
    "                lst.append(sorted_b[k])\n",
    "                lst.append(sorted_b[k+n//2])\n",
    "        if n%2!=0:\n",
    "            for k in range(n//2):\n",
    "                lst.append(sorted_b[k])\n",
    "                lst.append(sorted_b[k+ n//2 +1])   \n",
    "            lst.append(sorted_b[n//2])\n",
    "        return lst\n",
    "\n",
    "        55557\n",
    "        77788"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        cnt = Counter(barcodes)\n",
    "        barcodes.sort(key=lambda x: (-cnt[x], x))\n",
    "        n = len(barcodes)\n",
    "        ans = [0]*len(barcodes)\n",
    "        ans[::2]=barcodes[:(n+1)//2]\n",
    "        ans[1::2]=barcodes[(n+1)//2:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        cnt = Counter(barcodes)\n",
    "        barcodes.sort(key=lambda x: (-cnt[x], x))\n",
    "        n = len(barcodes)\n",
    "        ans = [0] * len(barcodes)\n",
    "        ans[::2] = barcodes[: (n + 1) // 2]\n",
    "        ans[1::2] = barcodes[(n + 1) // 2:]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        a = list(set(barcodes))\n",
    "        con = Counter(barcodes)\n",
    "        b = []\n",
    "        for j in a:\n",
    "            b.append([con[j], j])\n",
    "        b.sort()\n",
    "        bns = []\n",
    "        for i in range(len(a)):\n",
    "            for j in range(b[i][0]):\n",
    "                bns.append(b[i][1])\n",
    "        print(bns)\n",
    "        l = 0        \n",
    "        r = len(barcodes)//2\n",
    "        k = 0\n",
    "        ans = []\n",
    "        for i in range(len(barcodes)):\n",
    "            if k == 0:\n",
    "                ans.append(bns[r])\n",
    "                k += 1\n",
    "                r += 1\n",
    "            else:\n",
    "                ans.append(bns[l])\n",
    "                k -= 1\n",
    "                l += 1\n",
    "                \n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, arr: List[int]) -> List[int]:\n",
    "        cnt=Counter(arr)\n",
    "        n=len(arr)\n",
    "        arr.sort(key=lambda x:(-cnt[x],x))\n",
    "        res=[0]*n\n",
    "        m=(n+1)//2\n",
    "        a=arr[:m][::-1]\n",
    "        b=arr[m:][::-1]\n",
    "        for i in range(0,n,2):\n",
    "            res[i]=a.pop()\n",
    "        for i in range(1,n,2):\n",
    "            res[i]=b.pop()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:\n",
    "        a = list(set(barcodes))\n",
    "        con = Counter(barcodes)\n",
    "        b = []\n",
    "        for j in a:\n",
    "            b.append([con[j], j])\n",
    "        b.sort()\n",
    "        bns = []\n",
    "        for i in range(len(a)):\n",
    "            for j in range(b[i][0]):\n",
    "                bns.append(b[i][1])\n",
    "        print(bns)\n",
    "        l = 0\n",
    "        if len(barcodes)%2 == 0:\n",
    "            r = len(barcodes)//2\n",
    "        else:\n",
    "            r = len(barcodes)//2\n",
    "        k = 0\n",
    "        ans = []\n",
    "        for i in range(len(barcodes)):\n",
    "            if k == 0:\n",
    "                ans.append(bns[r])\n",
    "                k += 1\n",
    "                r += 1\n",
    "            else:\n",
    "                ans.append(bns[l])\n",
    "                k -= 1\n",
    "                l += 1\n",
    "                \n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
